package org.cabbage.lintcode;

public class MaxSubArray {

    public static void main(String[] args) {
        MaxSubArray msa = new MaxSubArray();
        System.out.println(msa.maxSubArray(new int[]{5, -10, 4}));

    }

    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sun = 0;
        for (int num : nums) {
            sun += num;
            if (max < sun) {
                max = sun;
            }
            if (sun < 0) {
                sun = 0;
            }
        }
        return max;
    }
}
